package com.itheima.datastructure.linkedlist;


import java.util.List;

//反转链表
public class E01Leetcode206 {
    //方法一
    public ListNode reverseList1(ListNode o1){
        ListNode n1=null;
        ListNode p=o1;
        while(p!=null){
            //一开始n1==null,所以重构n1时。next==null
            n1=new ListNode(p.val,n1);
            p=p.next;
        }
        return n1;
    }

    //方法二
    public ListNode reverseList2(ListNode head){
        //旧链表
        List list1=new List(head);
        //新链表
        List list2=new List(null);
        while(true){
            ListNode first=list1.removeFirst();
            if(first==null){
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }
    //构造方法二辅助链表结构
    static class List{
        //头结点
        ListNode head;

        public List(ListNode head){
            this.head=head;
        }
        //给新链表的头部添加节点
        public void addFirst(ListNode first){
            first.next=head;
            head=first;
        }
        //给旧链表的头结点移除掉
        public ListNode removeFirst(){
            ListNode first=head;
            if(first!=null){
                head=first.next;
            }
            return first;
        }
    }

    //方法三
    public ListNode reverseList3(ListNode p){
        if(p==null || p.next==null){
            return p;
        }
        ListNode last=reverseList3(p.next);
        //5->4 (p=4,p.next=5)
        p.next.next=p;
        //防止出现死循环（4->null)
        p.next=null;
        return last;
    }

    //方法四
    public ListNode reverseList4(ListNode o1) {
        //空链表或者只有一个元素
        if(o1==null || o1.next==null){
            return o1;
        }
        ListNode o2=o1.next;
        ListNode n1=o1;
        while(o2!=null){
            o1.next=o2.next;
            o2.next=n1;
            n1=o2;
            o2=o1.next;
        }
        return n1;
    }

    //方法五
    public ListNode reverseList5(ListNode o1){
        if(o1==null || o1.next==null){
            return o1;
        }
        ListNode n1=null;
        while(o1!=null){
            ListNode o2=o1.next;
            o1.next=n1;//将第一个元素移到新链表头部
            n1=o1;
            o1=o2;//恢复o1位置
        }
        return n1;
    }

    public static void main(String[] args){
        ListNode o5=new ListNode(5,null);
        ListNode o4=new ListNode(4,o5);
        ListNode o3=new ListNode(3,o4);
        ListNode o2=new ListNode(2,o3);
        ListNode o1=new ListNode(1,o2);

        System.out.println(o1);
        //ListNode n1=new E01Leetcode206().reverseList2(o1);
        ListNode n1=new E01Leetcode206().reverseList5(o1);
        System.out.println(n1);
    }

}
